package LinkedListSeries;

public class GetIntersectionNodeSolution_160_hot100_2 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 1、先得到两个链表的长度，差值假设为k
        // 2、让长链表指针先移动k步
        // 3、然后一起移动，找是否相同，不相同则一起后移
        ListNode curA = headA;
        ListNode curB = headB;

        int lenA = 0;
        int lenB = 0;

        while (curA != null) {
            curA = curA.next;
            lenA++;
        }
        while (curB != null) {
            curB = curB.next;
            lenB++;
        }

        curA = headA;
        curB = headB;

        // 强制确定curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;

            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }

        int k = lenA - lenB;
        //让A先走
        for (int i = 0; i < k; i++) {
            curA = curA.next;
        }

        while (curA != null) {
            if (curA == curB) {
                return curA;
            } else {
                curA = curA.next;
                curB = curB.next;
            }
        }
        return null;
    }
}
